// https://leetcode.cn/problems/multiply-strings/

// 题干：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，
//       它们的乘积也表示为字符串形式。
//       注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

// 示例：输入: num1 = "2", num2 = "3"
//       输出: "6"

// 碎语：高精度相乘的题目，还是模拟，掌握竖式乘法的规则
//       本质上传入字符串是因为防止数字过大
//       我们发现可以求出来几个字符串，再将几个字符串高精度相加即可
//       细节在于，高位相乘的时候，要补上'0'
//       处理前导0，比如说123*0的时候
//       注意计算结果的顺序

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    string multiply(string n1, string n2)
    {
        // 更优解法，先无进位相乘然后相加，最后处理进位
        // m长度和n长度的字符串，它们不进位相乘的位数最大位m+n-1
        // 放的位置与相乘的位数有映射关系，直接位数相加

        // 1.先无进位相乘
        int m = n1.size(), n = n2.size();
        reverse(n1.begin(), n1.end());
        reverse(n2.begin(), n2.end());
        vector<int> tmp(m + n - 1);

        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++){
                tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
            }
        }

        // 2.处理进位
        int cur = 0, carry = 0;
        string ret;
        while (cur < m + n - 1 || carry){
            if (cur < m + n - 1) carry += tmp[cur++];
            ret += carry % 10 + '0';
            carry /= 10;
        }

        // 处理前导0
        while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());

        return ret;
    }
};

int main()
{
    Solution sol;
    string n1 = "2", n2 = "3";

    string index = sol.multiply(n1, n2);
    cout << index << endl;

    return 0;
}











